package sorting;

public class QuickSort {

	static int[] array = new int[] { 5, 9, 4, 0, 14, 6, 14, 99, 3, 44, 17 };

	public static void main(String[] args) {

		quickSort(array);

		printArray(array);

	}

	private static void quickSort(int[] array) {
		sort(array, 0, array.length - 1);
	}

	private static void sort(int[] array, int l, int r) {

		int middle = (l + r) >> 1;
		int value = array[middle];

		int left = l;
		int right = r;

		while (left <= right) {
			while(array[left] < value) {
				left++;
			}
			while(array[right] > value) {
				right--;
			}
			
			if(left <= right) {
				swap(array, left, right);
				left++;
				right--;
			}
		}
		
		if(r > left) {
			sort(array, left, r);
		}
		if(l < right) {
			sort(array, l, right);
		}
	}

	private static void swap(int[] array, int i, int j) {
		int tmp = array[i];
		array[i] = array[j];
		array[j] = tmp;
	}

	private static void printArray(int[] array2) {
		for (int a : array) {
			System.out.print(a + " ");
		}
	}
}
